Date: Tuesday, 14-Jan-97 23:53:24 GMT
Server: NCSA/1.1
MIME-version: 1.0
Content-type: text/html
Last-modified: Monday, 30-Dec-96 16:50:10 GMT

<HTML>
<HEAD> 
    <TITLE>Recent Papers of Joe Mitchell</TITLE>
</HEAD> 
<BODY> 

<H2>Selected Papers of Joe Mitchell</H2> 

    <BR>
    <BR>


<HR>
<BR> 

J.S.B. Mitchell (1996):
<BR>
<!WA0><a href="ftp://ams.sunysb.edu/pub/geometry/survey-sp.ps.gz">
   ``Shortest Paths and Networks''</a>
<BR>
    Draft of a survey chapter for the CRC Handbook on Computational Geometry.
<BR>
  Feedback is greatly encouraged. 


<HR>
<BR> 

J.S.B. Mitchell (1996):
<BR>
<!WA1><a href="ftp://ams.sunysb.edu/pub/geometry/tsp.ps.gz">
   ``Guillotine Subdivisions Approximate Polygonal Subdivisions: 
<BR>
Part II -- A simple polynomial-time approximation scheme for geometric
k-MST, TSP, and related problems''</a>
<BR>
    Manuscript, April 1996. (Revised July, 1996)
<BR>
<!WA2><a href="ftp://ams.sunysb.edu/pub/geometry/tsp-talk.ps.gz">
    PostScript color transparencies of talk.</a>

<HR>
<BR> 

J.S.B. Mitchell (1996):
<BR>
   ``Guillotine Subdivisions Approximate Polygonal Subdivisions: 
A Simple New Method for the Geometric k-MST Problem''.
<BR>
    Appears in
<CITE>
    7th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'96),
</CITE>
<BR>
    Atlanta, GA, USA, Jan 28-30, 1996, pages 402--408.
<BR>
(See journal version below.)  Part I of two; see part II above.
<BR>
<!WA3><a href="ftp://ams.sunysb.edu/pub/geometry/guil-talk.ps.gz">
    PostScript color transparencies of talk.</a>


<HR>
<BR> 

J.S.B. Mitchell, A. Blum, P. Chalasani, S. Vempala (1996):
<BR>
<!WA4><a href="ftp://ams.sunysb.edu/pub/geometry/guil-full.ps.gz">
``A Constant-Factor Approximation Algorithm for the
Geometric k-MST Problem in the Plane''</a>
<BR>
    Journal version of above; last revision July 1996.

<HR>
<BR> 

<!WA5><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
Y-J. Chiang, 
J.S.B. Mitchell, S.S. Skiena, and T-C. Yang (1997):
<BR>
<!WA6><a href="ftp://ams.sunysb.edu/pub/geometry/scatter.ps.gz">
    ``On the Maximum Scatter TSP''</a>
<BR>
<CITE>
    8th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'97), to appear,
</CITE>
    New Orleans, LA, USA, Jan 5-7, 1997, pages ??.
<BR>
Full paper submitted to <CITE>JACM</CITE>

<HR>
<BR>

J.S.B. Mitchell (1996):
<BR>
<!WA7><a href="ftp://ams.sunysb.edu/pub/geometry/wacg96-abstract.ps.gz">
``On Some Applications of Computational
Geometry in Manufacturing and Virtual Environments''</a>
<BR>
Abstract of talk
(<!WA8><a href="ftp://ams.sunysb.edu/pub/geometry/wacg96-talk.ps.gz">
transparencies</a>)
at the 
<CITE>
Workshop on Applied Computational Geometry
</CITE>
<BR>
Part of FCRC'96, Philadelphia, May 27-28, 1996.


<HR>
<BR>

<!WA9><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
<!WA10><a href="http://www.cosy.sbg.ac.at/~held/held.html"> M. Held</a>,
J.S.B. Mitchell, S.S. Skiena (1995):
<BR>
<!WA11><a href="ftp://ams.sunysb.edu/pub/geometry/grasp.ps.gz">
    ``Recognizing Polygonal Parts from Width Measurements''</a>
<BR>
<CITE>
    Proc. 7th Canadian Conference on Computational Geometry,
</CITE>
<BR>
    C. Gold, J.-M. Robert (eds.), pp. 199-204; 
    Qu&eacutebec City, Qu&eacutebec, Canada, Aug 10-13, 1995.
<BR>
To appear, <CITE>Computational Geometry: Theory and Applications</CITE>

<HR>
<BR>

<!WA12><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
Y-J. Chiang, 
<!WA13><a href="http://www.cosy.sbg.ac.at/~held/held.html"> M. Held</a>,
J.S.B. Mitchell, V. Sacristan, S.S. Skiena, and T-C. Yang (1996):
<BR>
<!WA14><a href="ftp://ams.sunysb.edu/pub/geometry/hulls.ps.gz">
    ``On Minimum-Area Hulls''</a>
<BR>
<CITE>
    Proc. European Symposium on Algorithms (ESA'96), 
</CITE>
<BR>
Submitted to, <CITE>Algorithmica</CITE>

<HR>
<BR>


<!WA15><a href="http://www.cosy.sbg.ac.at/~held/held.html"> M. Held</a>,
J. Klosowski, 
J.S.B. Mitchell:
<BR>
<!WA16><a href="ftp://ams.sunysb.edu/pub/geometry/cccg95_VR.ps.gz">
    ``Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs''</a>
<BR>
<CITE>
    Proc. 7th Canadian Conference on Computational Geometry,
</CITE>
<BR>
    C. Gold, J.-M. Robert (eds.), pp. 205-210; 
    Qu&eacutebec City, Qu&eacutebec, Canada, Aug 10-13, 1995.

<HR>
<BR>

G. Barequet, B. Chazelle, L. Guibas, J.S.B. Mitchell, A. Tal:
<BR>
<!WA17><a href="ftp://ams.sunysb.edu/pub/geometry/boxtree.ps.gz">
``BOXTREE: A Hierarchical Representation for Surfaces in 3D''</a>
<BR>
<CITE>
EuroGraphics'96, 
</CITE>
<BR>
J. Rossignac and F. Sillion, eds., Blackwell Publishers,
Europgraphics Association, Volume 15, (1996), Number 3, pages C-387--C-484.

<HR>
<BR>

C. Silva, J.S.B. Mitchell, and A. Kaufman (1996):
<BR>
<!WA18><a href="ftp://ams.sunysb.edu/pub/geometry/volvis96.pic.ps.gz">
``Fast Rendering of Irregular Grids''</a>   
<BR>
<CITE>
     ACM-IEEE Symposium on Volume Visualization (VolVis'96), 
</CITE>
San Francisco, CA, Oct 28-29, 1996, pages 15-22 (color plate, page 97).

<HR>
<BR>

<!WA19><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
<!WA20><a href="http://www.cosy.sbg.ac.at/~held/held.html"> M. Held</a>, J.S.B. Mitchell, S.S. Skiena (1994):
<BR>
<!WA21><a href="ftp://ams.sunysb.edu/pub/geometry/esa94.ps.Z">
    ``Hamiltonian Triangulations for Fast Rendering''</a>
<BR>
<CITE>
    European Symposium on Algorithms (ESA'94),
</CITE>
<BR>
    Springer-Verlag, LNCS 855, J. van Leeuwen (ed.), pp. 36-47; 
<BR>
    Utrecht, The Netherlands, Sep 26-28, 1994.
<BR>
Full paper appears in <CITE>The Visual Computer</CITE>, 12(9), pp. 429--444, 1996.

<HR>
<BR>

J.S.B. Mitchell and E.L. Wynters :
<BR>
<!WA22><a href="ftp://ams.sunysb.edu/pub/geometry/bipart.ps.Z">
``Finding Optimal Bipartitions of Points and Polygons''</a>
<BR>
Extended abstract in Springer LNCS, Vol.  519,
(F. Dehne, J.-R. Sack, N. Santoro, eds.),
<BR>
<CITE>
Workshop on Algorithms and Data Structures (WADS'91),
</CITE>
Ottawa, Ontario, August 14-16, 1991, pp. 202-213.
<BR>
Full paper (above) is updated and corrects an error in the WADS abstract.

<HR>
<BR>

<!WA23><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
D. Halperin, K. Kedem, J.S.B. Mitchell, and N. Naor:
<BR>
<!WA24><a href="ftp://ams.sunysb.edu/pub/geometry/shared-endpoints.ps.Z">
``Arrangements of Line Segments that Share Endpoints: Single Face
Results''</a>
<BR>
<CITE> Discrete & Computational Geometry</CITE>, Vol. 13, Nos. 3-4, pp. 257-270,
<BR> 
Special Volume on discrete geometry dedicated to Laszlo Fejes Toth
(J. Pach and I. Barany, eds.), 1995.
<BR>
Original conference version was in 
<CITE> Proc. Seventh Annual ACM Symposium on
Computational Geometry</CITE>, 
<BR>
North Conway, NH, June 10-12, 1991,
pp. 324-333.  
(Conference version incorrectly claimed a bound of O(h log h).)

<HR>
<BR>

<!WA25><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
H. Meijer, J.S.B. Mitchell, D. Rappaport, and S.S. Skiena:
<BR>
<!WA26><a href="ftp://ams.sunysb.edu/pub/geometry/decision-trees.ps.gz">
``Decision Trees for Geometric Models''</a>
<BR> 
To appear in the <CITE>International Journal of Computational Geometry
and Applications</CITE>
<BR>
An earlier version appears in <CITE> Proc. Ninth Annual ACM
Symposium on Computational Geometry</CITE>, May, 1993, pp. 368-378.


<HR>
<BR>

<!WA27><a href="http://ams.sunysb.edu/~estie/estie.html"> E.M. Arkin</a>, 
M. Goodrich, J.S.B. Mitchell, D. Mount, C. Piatko, and S.S. Skiena:
<BR>
<!WA28><a href="ftp://ams.sunysb.edu/pub/geometry/classes.ps.gz">
``Point Probe Decision Trees for Geometric Concept
Classes''</a>
(two pages of <!WA29><a href="ftp://ams.sunysb.edu/pub/geometry/classes-figs.ps.gz">
FIGURES</a> are separate)
<BR> 
<CITE>Workshop on Algorithms and Data Structures</CITE>, August, 1993, pp. 95-106.


<HR>
<BR>

J.S.B. Mitchell, D. Mount, and S. Suri:
<BR>
<!WA30><a href="ftp://ams.sunysb.edu/pub/geometry/mitchell-mount-suri.ps.gz">
``Query-Sensitive Ray Shooting''</a>
<BR> 
<CITE> Proc. Tenth Annual ACM
Symposium on Computational Geometry</CITE>, June 6-8, 1994, pp. 359-368.
<BR>
To appear in the <CITE>International Journal of Computational Geometry
and Applications</CITE>

<HR>
<BR>

J.S.B. Mitchell and S. Suri:
<BR>
<!WA31><a href="ftp://ams.sunysb.edu/pub/geometry/nest.ps.gz">
``Separation and Approximation of Polyhedral Objects''</a>
<BR>
<CITE> Computational Geometry: Theory and Applications</CITE> 5(1995), 95--114.

<HR>
<BR>


J.S.B. Mitchell:
<BR>
<!WA32><a href="ftp://ams.sunysb.edu/pub/geometry/sep-TR.ps.gz">
``Approximation Algorithms for Geometric Separation Problems''</a>
<BR> 
<CITE> Technical Report, 1993.
</CITE>


L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and
J. S. Snoeyink:  
<BR>
<!WA33><a href="ftp://ams.sunysb.edu/pub/geometry/ghms.ps.gz">
``Approximating Polygons and Subdivisions with
Minimum Link Paths''</a>
<BR>
<CITE> Proc. Second Annual International
Symposium on Algorithms (SIGAL)</CITE>, December 16-18, 1991, Taipei,
Taiwan, R.O.C., pp. 151--162, Springer Lecture Notes in Computer
Science, Vol. 557.
<BR>
Full paper appears in <CITE> International Journal of Computational Geometry & Applications<?CITE>
Vol. 3, No. 4, December 1993, pp. 383--415.


<HR>
<ADDRESS>
    last modification of this page:  Tuesday, October 22, 1996  <BR>
    Joe Mitchell (<!WA34><A HREF="mailto:jsbm@ams.sunysb.edu">jsbm@ams.sunysb.edu</A>)
    <!-- (jsbm@ams.sunysb.edu) -->
</ADDRESS>




</BODY> 
</HTML> 
